def qsort(arr, left, right):
    if left >= right:
        return arr
    m = arr[left]
    i = left
    j = right
    while i != j:
        while arr[j] >= m and i < j:
            j -= 1
        while arr[i] <= m and i < j:
            i += 1
        if i < j:
           arr[i], arr[j] = arr[j], arr[i]

    arr[left] = arr[i]
    arr[i] = m
    qsort(arr, left, i-1)
    qsort(arr, i+1, right)
    return arr


def has(nums, target):
    if len(nums) == 0:
        return -1
    lower = 0
    upper = len(nums) - 1
    while True:
        mid = (lower + upper) / 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lower = mid + 1
        elif nums[mid] > target:
            upper = mid - 1
        if lower > upper:
            return -1


def twoSum(nums, target):
    nums = qsort(nums, 0, len(nums)-1)
    vals = []  # expected num index
    keys = []  # expected num
    for i in range(len(nums)):
        j = has(keys, nums[i])
        if j != -1:
            return i, j
        else:
            keys.append(target-nums[i])
            vals.append(i)

if __name__ == '__main__':
    r = twoSum([3, 2, 4], 6)
    print(r)
